// ioi_trainer.h
#ifndef IOI_TRAINER_H
#define IOI_TRAINER_H

#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <stack>
#include <queue>
#include <algorithm>
#include <iterator>
#include <functional>
#include <numeric>
#include <memory>
#include <utility>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cctype>
#include <cassert>
#include <climits>
#include <limits>
#include <bitset>
#include <complex>
#include <iomanip>

using namespace std;

// ==================== 基础类型定义 ====================
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pdd;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ld> vld;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef vector<vb> vvb;
typedef vector<pii> vpii;
typedef vector<pll> vpll;

// ==================== 常用常量 ====================
const int INF = 0x3f3f3f3f;
const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;
const int MOD = 1e9 + 7;
const int MOD998 = 998244353;
const double PI = acos(-1.0);
const double EPS = 1e-9;
const int dx[] = {-1, 0, 1, 0, -1, -1, 1, 1};
const int dy[] = {0, 1, 0, -1, -1, 1, -1, 1};

// ==================== 常用宏 ====================
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) ((int)(x).size())
#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define repd(i, a, b) for (int i = (a); i >= (b); --i)
#define repn(i, n) rep(i, 0, n)
#define repdn(i, n) repd(i, n-1, 0)
#define foreach(it, x) for (auto it = (x).begin(); it != (x).end(); ++it)

// ==================== 调试系统 ====================
#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", _debug(__VA_ARGS__)
#define debug_vec(v) cerr << #v << " = "; _debug_vec(v)
#define debug_mat(m) cerr << #m << " =\n"; _debug_mat(m)
#else
#define debug(...) ((void)0)
#define debug_vec(v) ((void)0)
#define debug_mat(m) ((void)0)
#endif

void _debug() { cerr << endl; }
template<typename T, typename... Args>
void _debug(T first, Args... args) {
    cerr << " " << first;
    _debug(args...);
}

template<typename T>
void _debug_vec(const vector<T>& v) {
    cerr << "[";
    for (size_t i = 0; i < v.size(); ++i) {
        if (i > 0) cerr << ", ";
        cerr << v[i];
    }
    cerr << "]" << endl;
}

template<typename T>
void _debug_mat(const vector<vector<T>>& m) {
    for (const auto& row : m) {
        for (const auto& x : row) {
            cerr << x << " ";
        }
        cerr << endl;
    }
}

// ==================== 快速IO ====================
class FastIO {
private:
    static const int BUFSIZE = 1 << 20;
    char inbuf[BUFSIZE], outbuf[BUFSIZE];
    int inpos, outpos, len;
    
    inline char getChar() {
        if (inpos == len) {
            len = fread(inbuf, 1, BUFSIZE, stdin);
            inpos = 0;
            if (len == 0) return EOF;
        }
        return inbuf[inpos++];
    }
    
    template<typename T>
    inline void readPositive(T &x) {
        x = 0;
        char c;
        while ((c = getChar()) < '0');
        do {
            x = x * 10 + (c - '0');
        } while ((c = getChar()) >= '0');
    }
    
    template<typename T>
    inline void readNegative(T &x) {
        x = 0;
        char c;
        while ((c = getChar()) < '0');
        do {
            x = x * 10 + (c - '0');
        } while ((c = getChar()) >= '0');
        x = -x;
    }

public:
    FastIO() : inpos(0), outpos(0), len(0) {}
    
    template<typename T>
    inline void read(T &x) {
        char c;
        while ((c = getChar()) <= ' ');
        if (c == '-') {
            readNegative(x);
        } else {
            x = c - '0';
            while ((c = getChar()) >= '0') {
                x = x * 10 + (c - '0');
            }
        }
    }
    
    inline void read(string &s) {
        s.clear();
        char c;
        while ((c = getChar()) <= ' ');
        do {
            s += c;
        } while ((c = getChar()) > ' ');
    }
    
    inline void read(char &c) {
        while ((c = getChar()) <= ' ');
    }
    
    inline void write(char c) {
        if (outpos == BUFSIZE) {
            fwrite(outbuf, 1, BUFSIZE, stdout);
            outpos = 0;
        }
        outbuf[outpos++] = c;
    }
    
    template<typename T>
    inline void write(T x) {
        if (x < 0) {
            write('-');
            x = -x;
        }
        char buf[20];
        int pos = 0;
        do {
            buf[pos++] = '0' + x % 10;
            x /= 10;
        } while (x > 0);
        while (pos > 0) {
            write(buf[--pos]);
        }
    }
    
    inline void write(const string &s) {
        for (char c : s) write(c);
    }
    
    ~FastIO() {
        if (outpos > 0) {
            fwrite(outbuf, 1, outpos, stdout);
        }
    }
};

// ==================== 数学函数 ====================
template<typename T>
inline T gcd(T a, T b) {
    while (b) {
        T t = b;
        b = a % b;
        a = t;
    }
    return a;
}

template<typename T>
inline T lcm(T a, T b) {
    return a / gcd(a, b) * b;
}

template<typename T>
inline T mod_pow(T a, T b, T mod = MOD) {
    T res = 1;
    a %= mod;
    while (b > 0) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

template<typename T>
inline T mod_inv(T a, T mod = MOD) {
    return mod_pow(a, mod - 2, mod);
}

inline bool is_prime(ll n) {
    if (n < 2) return false;
    if (n == 2 || n == 3) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;
    for (ll i = 5; i * i <= n; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0) return false;
    }
    return true;
}

// 组合数预处理
class Combinatorics {
private:
    int n;
    vll fact, inv_fact;
    
public:
    Combinatorics(int _n, ll mod = MOD) : n(_n), fact(_n + 1), inv_fact(_n + 1) {
        fact[0] = 1;
        rep(i, 1, n + 1) fact[i] = fact[i - 1] * i % mod;
        inv_fact[n] = mod_inv(fact[n], mod);
        repd(i, n - 1, 0) inv_fact[i] = inv_fact[i + 1] * (i + 1) % mod;
    }
    
    ll nCr(int n, int r, ll mod = MOD) {
        if (r < 0 || r > n) return 0;
        return fact[n] * inv_fact[r] % mod * inv_fact[n - r] % mod;
    }
    
    ll nPr(int n, int r, ll mod = MOD) {
        if (r < 0 || r > n) return 0;
        return fact[n] * inv_fact[n - r] % mod;
    }
};

// ==================== 数据结构 ====================
// 并查集
class DSU {
private:
    vi parent, rank, size;
    
public:
    DSU(int n) : parent(n), rank(n, 0), size(n, 1) {
        rep(i, 0, n) parent[i] = i;
    }
    
    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    
    bool unite(int x, int y) {
        int rx = find(x), ry = find(y);
        if (rx == ry) return false;
        
        if (rank[rx] < rank[ry]) {
            parent[rx] = ry;
            size[ry] += size[rx];
        } else if (rank[rx] > rank[ry]) {
            parent[ry] = rx;
            size[rx] += size[ry];
        } else {
            parent[ry] = rx;
            rank[rx]++;
            size[rx] += size[ry];
        }
        return true;
    }
    
    int get_size(int x) {
        return size[find(x)];
    }
    
    bool connected(int x, int y) {
        return find(x) == find(y);
    }
};

// 树状数组
class Fenwick {
private:
    vll tree;
    int n;
    
public:
    Fenwick(int _n) : n(_n), tree(_n + 1, 0) {}
    
    void update(int idx, ll delta) {
        for (; idx <= n; idx += idx & -idx) {
            tree[idx] += delta;
        }
    }
    
    ll query(int idx) {
        ll sum = 0;
        for (; idx > 0; idx -= idx & -idx) {
            sum += tree[idx];
        }
        return sum;
    }
    
    ll range_query(int l, int r) {
        return query(r) - query(l - 1);
    }
};

// 线段树（区间和，区间更新）
class SegmentTree {
private:
    vll tree, lazy;
    int n;
    
    void build(const vll& arr, int node, int start, int end) {
        if (start == end) {
            tree[node] = arr[start];
        } else {
            int mid = (start + end) / 2;
            build(arr, 2 * node, start, mid);
            build(arr, 2 * node + 1, mid + 1, end);
            tree[node] = tree[2 * node] + tree[2 * node + 1];
        }
    }
    
    void push_down(int node, int start, int end) {
        if (lazy[node] != 0) {
            tree[node] += lazy[node] * (end - start + 1);
            if (start != end) {
                lazy[2 * node] += lazy[node];
                lazy[2 * node + 1] += lazy[node];
            }
            lazy[node] = 0;
        }
    }
    
    void update_range(int node, int start, int end, int l, int r, ll val) {
        push_down(node, start, end);
        if (start > r || end < l) return;
        if (l <= start && end <= r) {
            lazy[node] += val;
            push_down(node, start, end);
        } else {
            int mid = (start + end) / 2;
            update_range(2 * node, start, mid, l, r, val);
            update_range(2 * node + 1, mid + 1, end, l, r, val);
            tree[node] = tree[2 * node] + tree[2 * node + 1];
        }
    }
    
    ll query_range(int node, int start, int end, int l, int r) {
        push_down(node, start, end);
        if (start > r || end < l) return 0;
        if (l <= start && end <= r) return tree[node];
        int mid = (start + end) / 2;
        return query_range(2 * node, start, mid, l, r) + 
               query_range(2 * node + 1, mid + 1, end, l, r);
    }

public:
    SegmentTree(const vll& arr) : n(arr.size()) {
        tree.resize(4 * n);
        lazy.resize(4 * n, 0);
        build(arr, 1, 0, n - 1);
    }
    
    void update(int l, int r, ll val) {
        update_range(1, 0, n - 1, l, r, val);
    }
    
    ll query(int l, int r) {
        return query_range(1, 0, n - 1, l, r);
    }
};

// ==================== 图论算法 ====================
// 图的邻接表表示
struct Graph {
    int n;
    vector<vpii> adj;  // 邻接表：目标节点，权重
    
    Graph(int _n) : n(_n), adj(_n) {}
    
    void add_edge(int u, int v, int w = 1) {
        adj[u].eb(v, w);
        adj[v].eb(u, w); // 无向图
    }
    
    void add_directed_edge(int u, int v, int w = 1) {
        adj[u].eb(v, w);
    }
};

// Dijkstra最短路径
vll dijkstra(const Graph& g, int start) {
    vll dist(g.n, INFLL);
    dist[start] = 0;
    priority_queue<pll, vpll, greater<pll>> pq;
    pq.emplace(0, start);
    
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue;
        
        for (auto [v, w] : g.adj[u]) {
            ll new_dist = dist[u] + w;
            if (new_dist < dist[v]) {
                dist[v] = new_dist;
                pq.emplace(new_dist, v);
            }
        }
    }
    return dist;
}

// ==================== 几何计算 ====================
struct Point {
    ll x, y;
    Point(ll x = 0, ll y = 0) : x(x), y(y) {}
    
    Point operator+(const Point& p) const { return Point(x + p.x, y + p.y); }
    Point operator-(const Point& p) const { return Point(x - p.x, y - p.y); }
    Point operator*(ll k) const { return Point(x * k, y * k); }
    Point operator/(ll k) const { return Point(x / k, y / k); }
    
    ll operator*(const Point& p) const { return x * p.x + y * p.y; } // 点积
    ll operator^(const Point& p) const { return x * p.y - y * p.x; } // 叉积
    
    bool operator==(const Point& p) const { return x == p.x && y == p.y; }
    bool operator<(const Point& p) const {
        return x < p.x || (x == p.x && y < p.y);
    }
    
    ld dist() const { return sqrt(x * x + y * y); }
    ld dist(const Point& p) const { return (*this - p).dist(); }
    ll dist2() const { return x * x + y * y; }
    ll dist2(const Point& p) const { return (*this - p).dist2(); }
};

// 计算多边形面积（鞋带公式）
ll polygon_area(const vector<Point>& poly) {
    ll area = 0;
    int n = poly.size();
    rep(i, 0, n) {
        int j = (i + 1) % n;
        area += poly[i] ^ poly[j];
    }
    return abs(area) / 2;
}

// ==================== 字符串算法 ====================
vi prefix_function(const string& s) {
    int n = s.length();
    vi pi(n, 0);
    rep(i, 1, n) {
        int j = pi[i - 1];
        while (j > 0 && s[i] != s[j]) {
            j = pi[j - 1];
        }
        if (s[i] == s[j]) j++;
        pi[i] = j;
    }
    return pi;
}

// KMP算法
vi kmp_search(const string& text, const string& pattern) {
    string combined = pattern + "#" + text;
    vi pi = prefix_function(combined);
    vi occurrences;
    int pattern_len = pattern.length();
    rep(i, pattern_len + 1, combined.length()) {
        if (pi[i] == pattern_len) {
            occurrences.pb(i - 2 * pattern_len);
        }
    }
    return occurrences;
}

// ==================== 实用函数 ====================
template<typename T>
inline void sort_unique(vector<T>& v) {
    sort(all(v));
    v.erase(unique(all(v)), v.end());
}

template<typename T>
inline int get_index(const vector<T>& v, const T& value) {
    auto it = lower_bound(all(v), value);
    if (it != v.end() && *it == value) {
        return it - v.begin();
    }
    return -1;
}

// 坐标压缩
template<typename T>
class CoordinateCompress {
private:
    vector<T> values;
    bool sorted;
    
public:
    CoordinateCompress() : sorted(false) {}
    
    void add(T x) {
        values.pb(x);
        sorted = false;
    }
    
    void build() {
        sort_unique(values);
        sorted = true;
    }
    
    int operator[](T x) {
        if (!sorted) build();
        return lower_bound(all(values), x) - values.begin();
    }
    
    int size() const {
        return values.size();
    }
    
    T get_value(int idx) {
        if (!sorted) build();
        return values[idx];
    }
};

#endif // IOI_TRAINER_H